"""
快速排序
时间复杂度：O(n log n) ,当列表为倒叙时。 时间复杂度为 O (log n²)

"""
import random


def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:  # 从右边找比tmp小的数
            right -= 1  # 往左一步
        li[left] = li[right]  # 把右边的值写带左边空位上
        print(li, 'right')
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]
        print(li, 'left')
    li[left] = tmp  # 把tmp归位
    return left


def quick_sort(li, left, right):
    if left < right:
        mid = partition(li, left, right)
        quick_sort(li, left, mid - 1)
        quick_sort(li, mid + 1, right)


if __name__ == '__main__':
    li = [5, 7, 4, 6, 3, 1, 2, 9, 8]
    print(li)
    quick_sort(li, 0, len(li) - 1)

    lis = list(range(10000))
    random.shuffle(lis)
    print(lis)
